<template>
  <section
    id="nice"
    data-tool="mdnice编辑器"
    data-website="https://www.mdnice.com"
    style="font-size: 16px; color: black; padding: 0 10px; line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; word-break: break-word; word-wrap: break-word; text-align: left; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, 'PingFang SC', Cambria, Cochin, Georgia, Times, 'Times New Roman', serif; margin-top: -10px;"
  >
    <h1
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 24px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content"
        >或许是一本可以彻底改变你刷 LeetCode 效率的题解书</span
      ><span class="suffix"></span>
    </h1>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      经过了半年时间打磨，投入诸多人力，这本 LeetCode
      题解书终于快要和大家见面了。目前已经完成了大部分章节的编写工作，预计经过一段时间的打磨就会和大家见面啦
      💐💐💐💐💐。
    </p>
    <h1
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 24px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">背景</span><span class="suffix"></span>
    </h1>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      自
      <a
        href="https://github.com/azl397985856/leetcode"
        style="text-decoration: none; word-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"
        >LeetCode 题解</a
      >
      （现在已经接近 30k star
      了）项目被大家开始关注，就有不少出版社开始联系我写书。刚开始后的时候，我并没有这个打算，觉得写这个相对于博客形式的题解要耗费时间，且并不一定效果比博客形式的效果好。后来当我向大家提及“出版社找我写书”这件事情的时候，很多人表示“想要买书，于是我就开始打算写这样一本书。但是一个完全没有写书经验的人，独立完成一本书工作量还是蛮大的，因此我打算寻求其他志同道合人士的帮助。
    </p>
    <h1
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 24px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">团队介绍</span><span class="suffix"></span>
    </h1>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      团队成员大都来自 985， 211 学校计算机系，大家经常参加算法竞赛，也坚持参加
      LeetCode
      周赛。在这个过程中，我们积累了很多经验，希望将这些经验分享给大家，以减少大家在刷题过程中的阻碍，让大家更有效率的刷题。
      本书尤其适合那些刚刚开始刷题的人，如果你刚开始刷题，或者刷了很多题面对新题还是无法很好的解决，那么这本书肯定很适合你。最后欢迎大家加入我们的读者群和作者进行交流。
    </p>
    <blockquote
      data-tool="mdnice编辑器"
      style="display: block; font-size: 0.9em; overflow: auto; overflow-scrolling: touch; border-left: 3px solid rgba(0, 0, 0, 0.4); color: #6a737d; padding-top: 10px; padding-bottom: 10px; padding-left: 20px; padding-right: 10px; margin-bottom: 20px; margin-top: 20px; border-left-color: rgb(239, 112, 96); background: #fff9f9;"
    >
      <p
        style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0px; color: black; line-height: 26px;"
      >
        读者群会在新书出版之后的第一时间开放。
      </p>
    </blockquote>
    <ul
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          <a
            href="https://leetcode-cn.com/u/hlxing/"
            style="text-decoration: none; word-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"
            >作者 - xing</a
          >
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          <a
            href="https://leetcode-cn.com/u/fe-lucifer/"
            style="text-decoration: none; word-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"
            >作者 - lucifer</a
          >
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          <a
            href="https://leetcode-cn.com/u/bruceyuj/"
            style="text-decoration: none; word-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"
            >作者 - BY</a
          >
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          <a
            href="https://www.fanlucloud.com/"
            style="text-decoration: none; word-wrap: break-word; font-weight: bold; color: rgb(239, 112, 96); border-bottom: 1px solid rgb(239, 112, 96);"
            >作者 - fanlu</a
          >
        </section>
      </li>
    </ul>
    <h1
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 24px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">样张</span><span class="suffix"></span>
    </h1>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      这里给大家开放部分章节内容给大家，让大家尝尝鲜。当然也欢迎大家提出宝贵的建议，帮助我们写出更好的内容。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      我们开放了第八章第五小节给大家看，以下是具体内容：
    </p>
    <h2
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; border-bottom: 2px solid rgb(239, 112, 96); font-size: 1.3em;"
    >
      <span class="prefix" style="display: none;"></span
      ><span
        class="content"
        style="display: inline-block; font-weight: bold; background: rgb(239, 112, 96); color: #ffffff; padding: 3px 10px 1px; border-top-right-radius: 3px; border-top-left-radius: 3px; margin-right: 3px;"
        >8.5 1206. 设计跳表</span
      ><span class="suffix"></span
      ><span
        style="display: inline-block; vertical-align: bottom; border-bottom: 36px solid #efebe9; border-right: 20px solid transparent;"
      >
      </span>
    </h2>
    <h3
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 20px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">题目描述</span
      ><span class="suffix" style="display: none;"></span>
    </h3>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      不使用任何库函数，设计一个跳表。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表是在
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span
      ></span>
      时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(N)"
            alt/></span></span
      >。跳表的每一个操作的平均时间复杂度是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span></span
      >，空间复杂度是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(N)"
            alt/></span></span
      >。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      在本题中，你的设计应该要包含这些函数：
    </p>
    <ul
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          bool search(int target) : 返回 target 是否存在于跳表中。
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          void add(int num):&nbsp; 插入一个元素到跳表。
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          bool erase(int num): 在跳表中删除一个值，如果 &nbsp;num&nbsp;
          不存在，直接返回 false. 如果存在多个
          &nbsp;num&nbsp;，删除其中任意一个即可。
        </section>
      </li>
    </ul>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      样例：
    </p>
    <pre
      class="custom"
      data-tool="mdnice编辑器"
      style="margin-top: 10px; margin-bottom: 10px;"
    ><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;">Skiplist skiplist = new Skiplist();

skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除
</code></pre>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      约束条件：
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >0 &lt;= num, target &lt;= 20000</code
      >
      最多调用 &nbsp;50000&nbsp; 次 &nbsp;search, add, 以及 &nbsp;erase 操作。
    </p>
    <h3
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 20px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">思路</span
      ><span class="suffix" style="display: none;"></span>
    </h3>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      首先，使用跳表会将数据存储成有序的。在数据结构当中，我们通常有两种基本的线性结构，结合有序数据，表达如下：
    </p>
    <ul
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          有序链表，我们有三种基本操作：
          <ul
            style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: square;"
          >
            <li>
              <section
                style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
              >
                查找指定的数据：时间复杂度为
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=O(N)"
                      alt/></span></span
                >,
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=N"
                      alt/></span
                ></span>
                为数据位于链表的位置。
              </section>
            </li>
            <li>
              <section
                style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
              >
                插入指定的数据：时间复杂度为
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=O(N)"
                      alt/></span></span
                >,
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=N"
                      alt/></span
                ></span>
                为数据位于链表的位置。因为插入数据之前，需要先查找到可以插入的位置。
              </section>
            </li>
            <li>
              <section
                style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
              >
                删除指定的数据：时间复杂度为
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=O(N)"
                      alt/></span></span
                >,
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=N"
                      alt/></span
                ></span>
                为数据位于链表的位置。因为删除数据之前，需要先查找到可以插入的位置。
              </section>
            </li>
          </ul>
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          有序数组：
          <ul
            style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: square;"
          >
            <li>
              <section
                style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
              >
                查找指定的数据：如果使用二分查找，时间复杂度为
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=O(logN)"
                      alt/></span></span
                >,
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=N"
                      alt/></span
                ></span>
                为数据的个数。
              </section>
            </li>
            <li>
              <section
                style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
              >
                插入指定的数据：时间复杂度为
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=O(N)"
                      alt/></span></span
                >,
                因为数组是顺序存储，插入新的数据时，我们需要向后移动指定位置后面的数据，这里
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=N"
                      alt/></span
                ></span>
                为数据的个数。
              </section>
            </li>
            <li>
              <section
                style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
              >
                删除指定的数据：时间复杂度为
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=O(N)"
                      alt/></span></span
                >,
                因为数组是顺序存储，删除数据时，我们需要向前移动指定位置后面的数据，这里
                <span class="span-inline-equation" style="cursor:pointer"
                  ><span
                    ><img
                      style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                      class="equation"
                      src="https://juejin.im/equation?tex=N"
                      alt/></span
                ></span>
                为数据的个数。
              </section>
            </li>
          </ul>
        </section>
      </li>
    </ul>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      而神奇的跳表能够在
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span
      ></span>
      时间内完成增加、删除、搜索操作。 下面我们分别分析增加、删除和搜索这 3
      个三个基本操作。
    </p>
    <h4
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 18px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">跳表的查找</span
      ><span class="suffix" style="display: none;"></span>
    </h4>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      现在我们通过一个简单的例子来描述跳表是如何实现的。假设我们有一个有序链表如下图：
      <img
        src="https://tva1.sinaimg.cn/large/00831rSTly1gdl834i5t2j33340ecdil.jpg"
        alt
        style="display: block; margin: 0 auto; width: auto; max-width: 100%;"
      />
      原始方法中，查找的时间复杂度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(N)"
            alt/></span></span
      >。那么如何来提高链表的查询效率呢？
      如下图所示，我们可以从原始链表中每两个元素抽出来一个元素，加上一级索引，并且一级索引指向原始链表：
      <img
        src="https://tva1.sinaimg.cn/large/00831rSTly1gdl81x0d7vj33340rbwjx.jpg"
        alt
        style="display: block; margin: 0 auto; width: auto; max-width: 100%;"
      />
      如果我们想要查找 9 ，在原始链表中查找路径是
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >1-&gt;3-&gt;4-&gt;7-&gt;9</code
      >, 而在添加了一级索引的查找路径是
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >1-&gt;4-&gt;9</code
      >，很明显，查找效率提升了。 按照这样的思路，我们在第 1 级索引上再加第 2
      级索引，再加第 3
      级索引，以此类推，这样在数据量非常大的时候，使得我们查找数据的时间复杂度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span></span
      >。这就是跳表的思想，也就是我们通常所说的“空间换时间”。
    </p>
    <h4
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 18px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">跳表的插入</span
      ><span class="suffix" style="display: none;"></span>
    </h4>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表插入数据看起来很简单，我们需要保持数据有序，因此，第一步我们需要像查找元素一样，找到新元素应该插入的位置，然后再插入。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      但是这样会存在一个问题，如果我们一直往原始链表中插入数据，但是不更新索引，那么会导致两个索引结点之间的数据非常多，在极端情况下，跳表会退化成单链表，从而导致查找效率由
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span
      ></span>
      退化为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(N)"
            alt/></span></span
      >。因此，我们需要在插入数据的同时，增加相应的索引或者重建索引。
    </p>
    <ol
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          方案
          1：每次插入数据后，将跳表的索引全部删除后重建，我们知道索引的结点个数为
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=N"
                alt/></span></span
          >（在空间复杂度分析时会有明确的数学推导），那么每次重建索引，重建的时间复杂度至少是
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=O(N)"
                alt/></span
          ></span>
          级别，很明显不可取。
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          方案 2：通过随机性来维护索引。假设跳表的每一层的提升概率为
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=\frac{1}{2}"
                alt/></span
          ></span>
          ，最理想的情况就是每两个元素提升一个元素做索引。而通常意义上，只要元素的数量足够多，且抽取足够随机的话，我们得到的索引将会是比较均匀的。尽管不是每两个抽取一个，但是对于查找效率来讲，影响并不很大。我们要知道，设计良好的数据结构往往都是用来应对大数据量的场景的。
          因此，我们这样维护索引：<strong
            style="font-weight: bold; color: black;"
            >随机抽取
            <span class="span-inline-equation" style="cursor:pointer"
              ><span
                ><img
                  style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                  class="equation"
                  src="https://juejin.im/equation?tex=\frac{N}{2}"
                  alt/></span
            ></span>
            个元素作为 1 级索引，随机抽取
            <span class="span-inline-equation" style="cursor:pointer"
              ><span
                ><img
                  style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                  class="equation"
                  src="https://juejin.im/equation?tex=\frac{N}{4}"
                  alt/></span
            ></span>
            作为 2 级索引，以此类推，一直到最顶层索引</strong
          >。
        </section>
      </li>
    </ol>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      那么具体代码该如何实现，才能够让跳表在每次插入新元素时，尽量让该元素有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{1}{2}"
            alt/></span
      ></span>
      的概率建立一级索引、<span
        class="span-inline-equation"
        style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{1}{4}"
            alt/></span
      ></span>
      的概率建立二级索引、<span
        class="span-inline-equation"
        style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{1}{8}"
            alt/></span
      ></span>
      的概率建立三级索引，以此类推。因此，我们需要一个概率算法。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      在通常的跳表实现当中，我们会设计一个
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >randomLevel()</code
      >
      方法，该方法会随机生成
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >1~MAX_LEVEL</code
      >
      之间的数 (MAX_LEVEL 表示索引的最高层数）
    </p>
    <ul
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          randomLevel() 方法返回 1
          表示当前插入的元素不需要建立索引，只需要存储数据到原始链表即可（概率
          1/2）
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          randomLevel() 方法返回 2 表示当前插入的元素需要建立一级索引（概率
          1/4）
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          randomLevel() 方法返回 3 表示当前插入的元素需要建立二级索引（概率
          1/8）
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          randomLevel() 方法返回 4 表示当前插入的元素需要建立三级索引（概率
          1/16）
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          ......
        </section>
      </li>
    </ul>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      可能有的同学会有疑问，我们需要一级索引中元素的个数时原始链表的一半，但是我们
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >randomLevel()</code
      >
      方法返回 2（建立一级索引）的概率是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{1}{4}"
            alt/></span></span
      >, 这样是不是有问题呢？ 实际上，只要<code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >randomLevel()</code
      >方法返回的数大于 1，我们都会建立一级索引，而返回值为 1 的概率是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{1}{2}"
            alt/></span></span
      >。所以，建立一级索引的概率其实是<span
        class="span-inline-equation"
        style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=1- \frac{1}{2} = \frac{1}{2}"
            alt/></span></span
      >。同上，当
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >randomLevel()</code
      >
      方法返回值
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >&gt;2</code
      >
      时，我们会建立二级或二级以上的索引，都会在二级索引中添加元素。而在二级索引中添加元素的概率是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=1- \frac{1}{2} - \frac{1}{4} = \frac{1}{4}"
            alt/></span></span
      >。 以此类推，我们推导出
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >randomLevel()</code
      >
      符合我们的设计要求。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      下面我们通过仿照 redis zset.c 的
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >randomLevel</code
      >
      的代码：
    </p>
    <pre
      class="custom"
      data-tool="mdnice编辑器"
      style="margin-top: 10px; margin-bottom: 10px;"
    ><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">##</span><br><span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;1.&nbsp;SKIPLIST_P&nbsp;为提升的概率，本案例中我们设置为&nbsp;1/2,&nbsp;如果我们想要节省空间利用效率，可以适当的降低该值，从而减少索引元素个数。在&nbsp;redis&nbsp;中&nbsp;SKIPLIST_P&nbsp;被设定为&nbsp;0.25。</span><br><span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;2.&nbsp;redis&nbsp;中通过使用位运算来提升浮点数比较的效率，在本案例中被简化</span><br><span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">randomLevel</span><span class="hljs-params" style="line-height: 26px;">()</span>:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;level&nbsp;=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;random()&nbsp;&lt;&nbsp;SKIPLIST_P&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;level&nbsp;&lt;&nbsp;MAX_LEVEL:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;level&nbsp;+=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;level<br></code></pre>
    <h4
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 18px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">跳表的删除</span
      ><span class="suffix" style="display: none;"></span>
    </h4>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表的删除相对来讲稍微简单一些。我们在删除数据的同时，需要删除对应的索引结点。
    </p>
    <h3
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 20px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">代码</span
      ><span class="suffix" style="display: none;"></span>
    </h3>
    <pre
      class="custom"
      data-tool="mdnice编辑器"
      style="margin-top: 10px; margin-bottom: 10px;"
    ><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; background: #282c34; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; border-radius: 0px; font-size: 12px; -webkit-overflow-scrolling: touch;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">from</span>&nbsp;typing&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">import</span>&nbsp;Optional<br><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">import</span>&nbsp;random<br><br><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">class</span>&nbsp;<span class="hljs-title" style="color: #e6c07b; line-height: 26px;">ListNode</span>:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">__init__</span><span class="hljs-params" style="line-height: 26px;">(self,&nbsp;data:&nbsp;Optional[int]&nbsp;=&nbsp;None)</span>:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._data&nbsp;=&nbsp;data&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;链表结点的数据域，可以为空（目的是方便创建头节点）</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._forwards&nbsp;=&nbsp;[]&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;存储各个索引层级中该结点的后驱索引结点</span><br><br><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">class</span>&nbsp;<span class="hljs-title" style="color: #e6c07b; line-height: 26px;">Skiplist</span>:</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;_MAX_LEVEL&nbsp;=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">16</span>&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;允许的最大索引高度，该值根据实际需求设置</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">__init__</span><span class="hljs-params" style="line-height: 26px;">(self)</span>:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._level_count&nbsp;=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;初始化当前层级为&nbsp;1</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._head&nbsp;=&nbsp;ListNode()<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._head._forwards&nbsp;=&nbsp;[<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">None</span>]&nbsp;*&nbsp;self._MAX_LEVEL<br><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">search</span><span class="hljs-params" style="line-height: 26px;">(self,&nbsp;target:&nbsp;int)</span>&nbsp;-&gt;&nbsp;bool:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;self._head<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span>&nbsp;i&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span>&nbsp;range(self._level_count&nbsp;-&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>):&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;从最高索引层级不断搜索，如果当前层级没有，则下沉到低一级的层级</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;p._forwards[i]&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;p._forwards[i]._data&nbsp;&lt;&nbsp;target:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p._forwards[i]<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">if</span>&nbsp;p._forwards[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>]&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;p._forwards[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>]._data&nbsp;==&nbsp;target:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">True</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">False</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">add</span><span class="hljs-params" style="line-height: 26px;">(self,&nbsp;num:&nbsp;int)</span>&nbsp;-&gt;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">None</span>:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;level&nbsp;=&nbsp;self._random_level()&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;随机生成索引层级</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">if</span>&nbsp;self._level_count&nbsp;&lt;&nbsp;level:&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;如果当前层级小于&nbsp;level,&nbsp;则更新当前最高层级</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._level_count&nbsp;=&nbsp;level<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new_node&nbsp;=&nbsp;ListNode(num)&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;生成新结点</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new_node._forwards&nbsp;=&nbsp;[<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">None</span>]&nbsp;*&nbsp;level<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update&nbsp;=&nbsp;[self._head]&nbsp;*&nbsp;self._level_count&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;用来保存各个索引层级插入的位置，也就是新结点的前驱结点</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;self._head<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span>&nbsp;i&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span>&nbsp;range(self._level_count&nbsp;-&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>):&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;整段代码获取新插入结点在各个索引层级的前驱节点，需要注意的是这里是使用的当前最高层级来循环。</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;p._forwards[i]&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;p._forwards[i]._data&nbsp;&lt;&nbsp;num:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p._forwards[i]<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update[i]&nbsp;=&nbsp;p<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span>&nbsp;i&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span>&nbsp;range(level):&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;更新需要更新的各个索引层级</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;new_node._forwards[i]&nbsp;=&nbsp;update[i]._forwards[i]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update[i]._forwards[i]&nbsp;=&nbsp;new_node<br><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">erase</span><span class="hljs-params" style="line-height: 26px;">(self,&nbsp;num:&nbsp;int)</span>&nbsp;-&gt;&nbsp;bool:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update&nbsp;=&nbsp;[<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">None</span>]&nbsp;*&nbsp;self._level_count<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;self._head<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span>&nbsp;i&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span>&nbsp;range(self._level_count&nbsp;-&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>):<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;p._forwards[i]&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;p._forwards[i]._data&nbsp;&lt;&nbsp;num:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p&nbsp;=&nbsp;p._forwards[i]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update[i]&nbsp;=&nbsp;p<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">if</span>&nbsp;p._forwards[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>]&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;p._forwards[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>]._data&nbsp;==&nbsp;num:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span>&nbsp;i&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span>&nbsp;range(self._level_count&nbsp;-&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>,&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>):<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">if</span>&nbsp;update[i]._forwards[i]&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;update[i]._forwards[i]._data&nbsp;==&nbsp;num:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update[i]._forwards[i]&nbsp;=&nbsp;update[i]._forwards[i]._forwards[i]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">True</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;self._level_count&nbsp;&gt;&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span>&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">not</span>&nbsp;self._head._forwards[self._level_count]:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self._level_count&nbsp;-=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;<span class="hljs-literal" style="color: #56b6c2; line-height: 26px;">False</span><br><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">_random_level</span><span class="hljs-params" style="line-height: 26px;">(self,&nbsp;p:&nbsp;float&nbsp;=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0.5</span>)</span>&nbsp;-&gt;&nbsp;int:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;level&nbsp;=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;random.random()&nbsp;&lt;&nbsp;p&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;level&nbsp;&lt;&nbsp;self._MAX_LEVEL:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;level&nbsp;+=&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">1</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;level<br></code></pre>
    <h3
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 20px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">复杂度分析</span
      ><span class="suffix" style="display: none;"></span>
    </h3>
    <h4
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 18px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">空间复杂度</span
      ><span class="suffix" style="display: none;"></span>
    </h4>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表通过建立索引提高查找的效率，是典型的“空间换时间”的思想，那么空间复杂度到底是多少呢？
      我们假设原始链表有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=N"
            alt/></span
      ></span>
      个元素，一级索引有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{2}"
            alt/></span></span
      >，二级索引有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{4}"
            alt/></span></span
      >，k 级索引有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{2^k}"
            alt/></span
      ></span>
      个元素，而最高级索引一般有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=2"
            alt/></span
      ></span>
      个元素。所以，索引结点的总和是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{2} + \frac{N}{2^2} + \frac{N}{2^3}+...+ 2 \approx N-2"
            alt/></span
      ></span>
      ，因此可以得出空间复杂度是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(N)"
            alt/></span></span
      >,
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=N"
            alt/></span
      ></span>
      是原始链表的长度。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      上面的假设前提是每两个结点抽出一个结点到上层索引。那么如果我们每三个结点抽出一个结点到上层索引，那么索引总和就是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{3} + \frac{N}{3^2} + \frac{N}{3^3} + 9 + 3 + 1 \approx \frac{N}{2}"
            alt/></span></span
      >,
      额外空间减少了一半。因此我们可以通过减少索引的数量来减少空间复杂度，但是相应的会带来查找效率一定的下降。而具体这个阈值该如何选择，则要看具体的应用场景。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      另外需要注意的是，在实际的应用当中，索引结点往往不需要存储完整的对象，只需要存储对象的
      key
      和对应的指针即可。因此当对象比索引结点占用空间大很多时，索引结点所占的额外空间（相对原始数据来讲）又可以忽略不计了。
    </p>
    <h4
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 18px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">时间复杂度</span
      ><span class="suffix" style="display: none;"></span>
    </h4>
    <h5
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 16px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">查找的时间复杂度</span
      ><span class="suffix" style="display: none;"></span>
    </h5>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      来看看时间复杂度
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span
      ></span>
      是如何推导出来的，首先我们看下图：
      <img
        src="https://tva1.sinaimg.cn/large/00831rSTly1gdl82ermgfj31rr0rs77h.jpg"
        alt
        style="display: block; margin: 0 auto; width: auto; max-width: 100%;"
      />
    </p>

    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      如上图所示，此处我们假设每两个结点会抽出一个结点来作为上一级索引的结点。也就是说，原始链表有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=N"
            alt/></span
      ></span>
      个元素，一级索引有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{2}"
            alt/></span></span
      >，二级索引有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{4}"
            alt/></span></span
      >，k 级索引有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=\frac{N}{2^k}"
            alt/></span
      ></span>
      个元素，而最高级索引一般有
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=2"
            alt/></span
      ></span>
      个元素。 也就是说：最高级索引
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=x"
            alt/></span
      ></span>
      满足
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=2 = N/2^x"
            alt/></span></span
      >, 由此公式可以得出
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=x = \log_2(N)-1"
            alt/></span
      ></span>
      , 加上原始数据这一层， 跳表的总高度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=h = \log_2(N)"
            alt/></span></span
      >。
      那么，我们在查找过程中每一层索引最多遍历几个元素呢？从图中我们可以看出来每一层最多需要遍历
      3 个结点。 因此，由公式
      <code
        style="font-size: 14px; word-wrap: break-word; padding: 2px 4px; border-radius: 4px; margin: 0 2px; background-color: rgba(27,31,35,.05); font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; word-break: break-all; color: rgb(239, 112, 96);"
        >时间复杂度 = 索引高度*每层索引遍历元素个数</code
      >， 可以得出跳表中查找一个元素的时间复杂度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(3 \times \log(N))"
            alt/></span></span
      >，省略常数即为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(\log(N))"
            alt/></span></span
      >。
    </p>
    <h5
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 16px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">插入的时间复杂度</span
      ><span class="suffix" style="display: none;"></span>
    </h5>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表的插入分为两部分操作：
    </p>
    <ol
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          寻找到对应的位置，时间复杂度为
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=O(logN)"
                alt/></span></span
          >,
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=N"
                alt/></span
          ></span>
          为链表长度。
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          插入数据。我们在前面已经推导出跳表索引的高度为
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=logN"
                alt/></span></span
          >。 因此，我们将数据插入到各层索引中的最坏时间复杂度为
          <span class="span-inline-equation" style="cursor:pointer"
            ><span
              ><img
                style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
                class="equation"
                src="https://juejin.im/equation?tex=O(logN)"
                alt/></span></span
          >。
        </section>
      </li>
    </ol>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      综上所述，插入操作的时间复杂度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span
      ></span>
    </p>
    <h5
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 16px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">删除的时间复杂度</span
      ><span class="suffix" style="display: none;"></span>
    </h5>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      跳表的删除操作和查找类似，只是需要在查找后删除对应的元素。查找操作的时间复杂度是
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=logN"
            alt/></span></span
      >。那么后面删除部分代码的时间复杂度是多少呢？我们知道在跳表中，每一层索引都是一个有序的单链表，而删除单个元素的复杂度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(1)"
            alt/></span></span
      >, 索引层数为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=logN"
            alt/></span></span
      >，因此删除部分代码的时间复杂度为<span
        class="span-inline-equation"
        style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=logN"
            alt/></span></span
      >。那么删除操作的总时间复杂度为-
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN) + O(logN) = 2O(logN)"
            alt/></span></span
      >。我们忽略常数部分，删除元素的时间复杂度为
      <span class="span-inline-equation" style="cursor:pointer"
        ><span
          ><img
            style="margin: 0 auto; width: auto; max-width: 100%; display: inline;"
            class="equation"
            src="https://juejin.im/equation?tex=O(logN)"
            alt/></span></span
      >。
    </p>
    <h3
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 20px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">扩展</span
      ><span class="suffix" style="display: none;"></span>
    </h3>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      在工业上，使用跳表的场景很多，下面做些简单的介绍，有兴趣的可以深入了解：
    </p>
    <ol
      data-tool="mdnice编辑器"
      style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: decimal;"
    >
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          redis 当中 zset 使用了跳表
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          HBase MemStore 当中使用了跳表
        </section>
      </li>
      <li>
        <section
          style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;"
        >
          LevelDB 和 RocksDB 都是 LSM Tree 结构的数据库，内部的 MemTable
          当中都使用了跳表
        </section>
      </li>
    </ol>
    <h1
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 24px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">配套网站</span><span class="suffix"></span>
    </h1>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      等新书发布之后，我们会在官网开辟一个区域，大家可以直接访问查看本书配套的配套代码，包括
      JavaScript，Java，Python 和 C++。
      也欢迎大家留言给我们自己想要支持的语言，我们会郑重考虑大家的意见。
    </p>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      效果大概是这样的：
    </p>
    <figure
      data-tool="mdnice编辑器"
      style="margin: 0; margin-top: 10px; margin-bottom: 10px;"
    >
      <img
        src="https://tva1.sinaimg.cn/large/00831rSTly1gdl80ojj2rj31tw0u00x1.jpg"
        alt
        style="display: block; margin: 0 auto; width: auto; max-width: 100%;"
      />
    </figure>
    <h1
      data-tool="mdnice编辑器"
      style="margin-top: 30px; margin-bottom: 15px; font-weight: bold; color: black; font-size: 24px;"
    >
      <span class="prefix" style="display: none;"></span
      ><span class="content">预定</span><span class="suffix"></span>
    </h1>
    <p
      data-tool="mdnice编辑器"
      style="font-size: 16px; padding-top: 8px; padding-bottom: 8px; margin: 0; line-height: 26px; color: black;"
    >
      如果你也想要第一时间获取到我们的题解新书，那么请发送邮件到
      azl397985856@gmail.com，标题著明“书籍《LeetCode 题解》预定”字样。
    </p>
  </section>
</template>
